Theo tài liệu lịch sử lưu trữ tại địa phương ghi nhận, những người đầu tiên định cư ở Oudômxai vào khoảng năm 700 là "Khom" tức người Khmu. Khoảng năm 1260, người Lao Ly đến từ vùng Sipsong Panna ở miền nam Trung Quốc, họ xây dựng một ngôi làng gọi là Bản Luang Cheng (gọi là "làng lớn" hoặc "huyện lớn") trong địa phận của tỉnh lị Thị xã Xai ngày nay. Làng Lao Ly cũ nay là một phần của Muang Xay và được gọi là Bang Cheng

Văn hoá Lý đã được đánh dấu bằng đạo Phật và những truyền thống cũ của người Khom, theo thời gian, nó được củng cố và ảnh hưởng đến toàn bộ khu vực này. Người Khom và người Leu sống cùng nhau và chia sẻ những khu vực trồng lúa. Để bảo đảm an toàn họ đã xây dựng các công sự phòng hộ giữa các làng Na Sao và Na Lai. Khoảng năm 1828, các bộ lạc Hmong đến từ Trung Quốc bắt đầu định cư tại Oudômxai. Tỉnh Oudômxai hiện nay được thành lập vào năm 1976, nó được tách ra từ Luang Prabang. Khoảng năm 1987, thủ phủ của tỉnh đã được chuyển từ Ban Nahin đến Muang Xay. Năm 1992, các huyện Paktha và huyện Pha Oudom được cắt sang tỉnh Bokeo.